// @algorithm @lc id=100276 lang=cpp
// @title er-wei-shu-zu-zhong-de-cha-zhao-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
// @test([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],5)=true
public:
    bool findNumberIn2DArray(vector<vector<int>> &matrix, int target) {
        int m = matrix.size();
        if (m == 0) {
            return false;
        }
        int n = matrix[0].size();
        int i = 0;
        int j = n - 1;
        while (i >= 0 && i < m && j >= 0 && j < n) {
            if (matrix[i][j] == target) {
                return true;
            }
            else if (matrix[i][j] > target) {
                --j;
            }
            else {
                ++i;
            }
        }
        return false;
    }
};